package LeetCode;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}18:47
 */
public class Bag01 {
    /**
     *
     * @param weight 每个背包的重量
     * @param value 每个背包的价值
     * @param C 容纳的量
     * @return
     */
    public static int knapsack01(int[] weight,int[] value,int C){
        if (weight.length != value.length){
            return -1;
        }
        int[][] dp = new int[2][C + 1];
        // 优化
        int[] dp2 = new int[C + 1];
        for (int i = 0; i < dp2.length; i++){
            if (i > weight[0]){
                dp2[i] = value[0];
            }
        }
        for (int i = 1; i < weight.length; i++){
            for (int j = C; j >= weight[i]; j--){
                dp2[j] = Math.max(dp2[j],value[i] + dp2[j - weight[i]]);
            }
        }


        for (int i = 0; i < 2; i++){
            dp[i][0] = 0;
        }
        for (int i = 0; i <= C; i++){
            if (i < weight[0]){
                continue;
            }
            dp[0][i] = value[0];
        }
        for (int i = 1; i < value.length; i++){//每行
            for (int j = 0; j <= C; j++){//这是递归的容积  每列
                dp[i % 2][j] = dp[(i - 1) % 2][j];//首先一定会放下之前一个物品，所以以此为标准
                if (j >= weight[i]){
                    dp[i % 2][j] = Math.max(dp[i % 2][j],value[i] + dp[(i - 1) % 2][j - weight[i]]);
                }
            }
        }
//        return dp[(weight.length - 1) % 2][C];
        return dp2[C];
    }


    public static void main(String[] args) {
        int[] weight = {10,2,5,6};
        int[] value = {12,10,5,8};
        System.out.println(knapsack01(weight, value, 9));
    }
}
